package com.cqs.leetcode;

/**
 * Created by cqs on 2018/3/26.
 */
public class MagicDictionary {

    //字典树
    private final Trie root;

    //节点
    private class Trie {
        char value;
        int count;
        Trie[] children = new Trie[26];

        Trie(char value, int count) {
            this.value = value;
            this.count = count;
        }
    }


    /**
     * Initialize your data structure here.
     */
    public MagicDictionary() {
        root = new Trie('$', 0);
    }

    /**
     * Build a dictionary through a list of words
     */
    public void buildDict(String[] dict) {
        for (int i = 0; i < dict.length; i++) {
            insert(dict[i]);
        }
    }


    private void insert(String word) {
        if (word != null) {
            Trie trie = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                if (trie.children[index] == null) {
                    trie.children[index] = new Trie(c, 0);
                }
                trie = trie.children[index];
            }
            trie.count++;
        }
    }


    /**
     * Returns if there is any word in the trie that equals to the given word after modifying exactly one character
     */

    public boolean search(final String word) {
        if (word != null) {
            return search(root, word, 0, 0);
        }
        return false;
    }

    //递归查询
    private boolean search(Trie parent, String word, int pos, int times) {
//        System.out.println(word + "\tpos:" + pos + "\ttimes:" + times);
        //有且仅有一个字符与原字符串不同
        if (times == 1) {
            for (int i = pos; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 97;
                parent = parent.children[index];
                if (parent == null || parent.value != c) {
                    return false;
                }
            }
//            System.out.println(word + " is Magic  ? " + (parent.count > 0));
            return parent.count > 0;
        }
        char c = word.charAt(pos);
        int index = c - 97;
        //parent节点最多有26个孩子节点  每个孩子节点均有才能采用
        for (int i = 0; i < 26; i++) {
            Trie node = parent.children[i];
            if (index == i) {
                //若前word.length() - 1个字符和word均相同 那么最后一个字符一定不能相同
                if ((pos != word.length() - 1) && node != null && node.value == c) {
                    boolean search = search(node, word, pos + 1, 0);
                    if (search) return true;
                }
            } else {
                //不为空 表示有兄弟节点
                if (node != null) {
                    boolean result = search(node, word, pos + 1, 1);
                    //找个符合条件的字符串 立即返回
                    if (result) return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        MagicDictionary md = new MagicDictionary();
        String[] data = {"hello", "leetcode"};
        md.buildDict(data);
//        print("hell", md);
//        print("hellp", md);
        print("hello", md);
        print("hallo", md);
        print("leetcoded", md);
    }

    static void print(String word, MagicDictionary md) {
        System.out.println(word + "\t" + md.search(word));
    }

    ;

}
